


#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

class Solution
{
public:
    int subarraySum1(vector<int>& nums, int k)
    {
        int res = 0;
        int n = nums.size();

        for (int i = 0, sum = 0; i < n; ++i)
        {
            sum = 0;
            for (int j = i; j < n; ++j)
            {
                sum += nums[j];
                if (sum == k)
                    ++res;
            }
        }

        return res;
    }

    int subarraySum2(vector<int>& nums, int k)
    {
        int res = 0;
        int n = nums.size();
        vector<int> prefix(n + 1);

        for (int i = 1; i <= n; ++i)
        {
            prefix[i] = prefix[i - 1] + nums[i - 1];
        }

        for (int i = 0; i < n; ++i)
        {
            for (int j = i, sum = 0; j < n; ++j)
            {
                sum = prefix[j + 1] - prefix[i];
                if (sum == k)
                    ++res;
            }
        }

        return res;
    }

    int subarraySum3(vector<int>& nums, int k)
    {
        int res = 0;
        unordered_map<int, int> hash;

        ++hash[0];
        for (int end = 0, prefixsum = 0, n = nums.size(); end < n; ++end)
        {
            prefixsum += nums[end];

            if (hash.count(prefixsum - k))
                res += hash[prefixsum - k];
            ++hash[prefixsum];
        }

        return res;
    }

    vector<int> spiralOrder(vector<vector<int>>& matrix)
    {
        int m = matrix.size(), n = matrix[0].size();
        if (1 == m)
            return matrix[0];

        vector<int> res;
        int left = 0, right = n - 1;
        int top = 0, bottom = m - 1;

        res.reserve(m * n);
        while (left <= right && top <= bottom)
        {
            for (int i = left; i <= right; ++i)
            {
                res.push_back(matrix[top][i]);
            }
            ++top;

            for (int i = top; i <= bottom; ++i)
            {
                res.push_back(matrix[i][right]);
            }
            --right;

            for (int i = right; top <= bottom && i >= left; --i)
            {
                res.push_back(matrix[bottom][i]);
            }
            --bottom;

            for (int i = bottom; left <= right && i >= top; --i)
            {
                res.push_back(matrix[i][left]);
            }
            ++left;
        }

        return res;
    }
};

void Test1()
{
    int k = 2;
    vector<int> v = {1, 1, 1};
   
    Solution().subarraySum2(v, k);

    vector<vector<int>> matrix1 = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} };
    vector<vector<int>> matrix2 = { {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12} };
    

    Solution().spiralOrder(matrix2);
}

int main()
{
    Test1();

	return 0;
}